package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/28/20
 * @Version 1.0
 */

import java.util.Arrays;

/**
 * 基数排序
 * 非原地排序，为了确保稳定性，对每一位用计数排序
 * 稳定算法
 * 时间复杂度为O(kn)，k是数组的位数
 *
 * 要求排序的数据是等长的。不登场要补齐
 * 数据要可以分割出独立的“位”来比较
 * 每一位的数据范围都不能太大，要能用线性排序算法来排序。
 *
 * @author jane
 */
public class RadixSort {

    public static int[] sort(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }
        int len = arr.length;
        int max = getMax(arr, len);

        int exp=1;
        while (max/exp>0){
            arr = sortByBit(arr,len,exp);
            exp*=10;
        }
        return arr;
    }

    /**
     * 对每一位进行计数排序
     * @param arr
     * @param len
     * @param exp
     */
    private static int[] sortByBit(int[] arr, int len, int exp){
        int[] bitCount = new int[10];//这里默认给整数排序，如果是其它类型，如char，则要计算最大最小值
        Arrays.fill(bitCount,0);
        int[] bitArray = new int[len];
        for(int i=0;i<len;i++){
            int bit = getBit(arr[i],exp);
            bitArray[i]=bit;
            bitCount[bit]++;
        }
        for(int i=1;i<10;i++){
            bitCount[i]+=bitCount[i-1];
        }
        int[] result = new int[len];
        for(int j=len-1;j>=0;j--){
            result[--bitCount[bitArray[j]]]=arr[j];
        }
        return result;
    }


    private static int getBit(int value, int exp){
        return (value/exp)%10;
    }

    private static int getMax(int[] arr, int len){
        int max=arr[0];
        for(int i=1;i<len;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }

        return max;
    }


}
